Figure 1. Nontransitive dice from the Grand Illusions site.
Ed Pegg Jr., July 11, 2005
Consider the three dice below, offered by Tim Rowett's Grand Illusions site. You get a choice of whichever die you want, then I pick one of the remaining dice. We each roll ten times, and whoever scores high the most times, wins. The dice are numbered {Red 144444, Green 222555, Blue 333336). Which one should you pick?
Figure 1. Nontransitive dice from the Grand Illusions site.
As you might suspect, if you've read Ivars Peterson's column Tricky Dice, any first choice can be beaten. In a typical game, Red loses to Green, Green loses to Blue, and Blue loses to Red. When you take that out to ten games, the edge becomes much more prominent.
Figure 2. A diagram of how the wins play out with each color pairing.
With two sets of dice, a baffling trick can be performed. After convincing a person of Green over Red over Blue over Green, you can pull out a second set of the same dice. This time, two dice of a color will be rolled. Tell your opponent that you'll pick a color first, and then they pick a color of their choice. If they follow the earlier lesson, they're trapped. In the 1296 possible games for two dice, the dominance reverses!
Figure 3. A diagram of wins with two dice versus two dice. (Winning half needs 648 total)
You can read more about nontransitive dice at MathWorld's entries Efron's Dice, or within the chapters of Martin Gardner's Mathematical Games Complete Collection from the MAA store. Searching for "nontransitive" on the Gardner CD reveals many interesting facts.
M. Oskar van Deventer learned of nontransitive dice in 1986. Recently, he tried to extend the game to three players. This time, there are seven dice, and two opponents. Each of the others picks a die of their choice, then you pick a third die. Ten times, all three of you roll the three dice. Is there a set of dice that allows you to beat both opponents -- a three-player non-transitive set of dice? Oskar came up with the set of dice below.
Figure 4. Oskar's 3-player nontransitive dice.
Here is a diagram of how Oskar's dice dominate each other, and a Fano plane that picks the winning die.
Figure 5. How Oskar's dice compare with each other, and a Fano plane for picking the winner.
For example, A&C are on the cyan circle, so cyan die F is the winner. If your opponents pick B&G, those are on the grey line, so grey die E wins.
Oskar wanted to extend this to four players. What dice make a non-transitive four player game, so that if three dice are chosen, a fourth die in the set beats all three? How many dice are needed for a five player non-transitive game, or more?
The graph seen above is a directed graph -- it has arrows on each edge between letters. A directed graph and digraph are the same thing. When a digraph is complete - with an arrow between any pair of points, it's called a Tournament graph. In a round-robin tournament (each player plays everyone else), these arrows show which player won.
The Schutte Tournament Problem asks for the smallest n-player nontransitive graph. To beat 3 other players, you'll need at least 19 dice. A tournament graph for this is below, which black/grey lines instead of arrows.
Figure 6. A Schutte tournament for 4 players. For any three players, there is a fourth that beats all of them.
A construction for this unique graph comes from number theory. An integer a is a quadratic residue modulo n if an x exists such that a ≡ x2 (mod n). For a prime p such that p ≡ 3 (mod 4), we know that i is a quadratic residue if and only if p-i is not a quadratic residue. Given a prime p ≡ 3 (mod 4), the quadratic residues modulo p form a rotational p-tournament. {1, 4, 5, 6, 7, 9, 11, 16, 17} are the quadratic residues of 19. 1≡12(mod 19), 4≡22(mod 19), 5≡92(mod 19), 6≡52(mod 19), 7≡82(mod 19), 9≡32(mod 19), 11≡72(mod 19), 16≡ 42(mod 19), 17≡62(mod 19). The same thing is happening with the 3 player game above -- the quadratic residues of 7 are {1,2,4}.
Oskar hasn't found a nice set of 19 dice for the 4 player game, yet. Also, the optimal graph is unknown for the 5 player game and above. If you solve either of these problems, please feel free to contact me.
Noga Alon, Graham Brightwell, H. A. Kierstead, A. V. Kostochka, Peter Winkler, "Dominating Sets in k-Majority Tournaments," CDAM Research Report LSE-CDAM-2004-11, June 2004. http://www.cdam.lse.ac.uk/Reports/Files/cdam-2004-11.pdf.
Martin Gardner, "Nontransitive Paradoxes," Time travel and other mathematical bewilderments. Complete Mathematical Games CD, MAA Store.
Martin Gardner, "Nontransitive Dice and Other Probability Paradoxes," Wheels, life, and other mathematical amusements. Complete Mathematical Games CD, MAA Store.
Martin Gardner, "Directed Graphs and Cannibals," The Last Recreations: Hydras,Eggs, and Other Mathematical Mystifications. Complete Mathematical Games CD, MAA Store.
Ivars Peterson, "Tricky Dice Revisited," April 13, 2002. http://se02.xif.com/articles/20020413/mathtrek.asp.
Tim Rowett, "Nontransitive Dice Set 2," Grand Illusions store. http://www.grand-illusions.com/magicdice.htm.
Dustin J. Stewart, "Domination And Matrix Properties In Tournaments Generalized Tournaments." Thesis, U of Colo, 2005. http://www-math.cudenver.edu/graduate/thesis/dstewart_thesis.pdf.
Eric W. Weisstein. "Efron's Dice." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EfronsDice.html
Comments are welcome. Please send comments to Ed Pegg Jr. at ed@mathpuzzle.com.
Ed Pegg Jr. is the webmaster for mathpuzzle.com. He works at Wolfram Research, Inc. as an associate editor of MathWorld, and as administrator of the Mathematica Information Center.